#include <vector>
using namespace std;
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ret;
        int n=matrix.size();
        if (n==0) return ret;
        int m=matrix[0].size();
        if (m==0) return ret;
        const int way[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
        vector<vector<bool> > used(n, vector<bool>(m, false));
        for (int i=0,x=0,y=-1,k=0;i<n*m;i++)
            while (true) {
                int nx=x+way[k][0], ny=y+way[k][1];
                if (0<=nx && nx<n && 0<=ny && ny<m && !used[nx][ny]) {
                    used[nx][ny]=true;
                    x=nx;
                    y=ny;
                    ret.push_back(matrix[x][y]);
                    break;
                } else k=(k+1)%4;
            }
        return ret;
    }
};
